package leetcode_二叉树;

import general_class.TreeNode;

/**
 * 最长同值路径
 * 算法：递归
 * 最长路径是 倒 v 字形, 即从结点的左子树经过结点到右子树
 * 求出当前结点的左子树和右子树的最长同值路径
 *
 * @author yezh
 * @date 2024/4/7 9:40
 */
public class _687 {

    int ans = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode node) {
        if (node == null) return 0;
        int res = 0, cur = 0, left = dfs(node.left), right = dfs(node.right);
        if (node.left != null && node.left.val == node.val) {
            res = left + 1;
            cur += left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            res = Math.max(res, right + 1);
            cur += right + 1;
        }
        ans = Math.max(ans, cur);
        return res;
    }

}
